import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def f(u, v):
return u * n + v
n = int(input())
n2 = n * n
dp = [[0] * n2 for _ in range(n2)]
for i in range(n):
s = list(input().rstrip())
for j in range(n):
if s[j] & 1:
dp[f(i, i)][f(j, j)] = 1
for l in range(n):
for r in range(n):
if not max(l, r):
continue
x = max(l, r) + 1
for i in range(n - l):
u = f(i, i + l)
for j in range(n - r):
v = f(j, j + r)
dp0 = x
for y in range(l):
dp0 = min(dp0, dp[f(i, i + y)][v] + dp[f(i + y + 1, i + l)][v])
for y in range(r):
dp0 = min(dp0, dp[u][f(j, j + y)] + dp[u][f(j + y + 1, j + r)])
dp[u][v] = dp0
ans = dp[f(0, n - 1)][f(0, n - 1)]
print(ans)#include<bits/stdc++.h>
#define INT long long
#define x first
#define y second
using namespace std;
const int NN = 55;
const int inf = 1e9 + 7;
const int Md = 650;
typedef pair<int , int> pii;
int n , m , k;
char A[NN][NN];
int dp[NN][NN][NN][NN];
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
int T;
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%s",A[i] + 1);
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
if(A[i][j] == '#') dp[i][j][i][j] = 1;
for(int ii = i; ii >= 1; ii --){
for(int jj = j; jj >= 1; jj --){
if(i == ii && j == jj) continue;
dp[i][j][ii][jj] = max(i - ii + 1 , j - jj + 1);
for(int md = i - 1; md >= ii; md --){
dp[i][j][ii][jj] = min(dp[i][j][ii][jj] , dp[i][j][md + 1][jj] + dp[md][j][ii][jj]);
}
for(int md = j - 1; md >= jj; md --){
dp[i][j][ii][jj] = min(dp[i][j][ii][jj] , dp[i][j][ii][md + 1] + dp[i][md][ii][jj]);
}
}
}
}
}
cout << dp[n][n][1][1] << endl;
return 0;
}
230B - T-primes | 630A - Again Twenty Five |
1234D - Distinct Characters Queries | 1183A - Nearest Interesting Number |
1009E - Intercity Travelling | 1637B - MEX and Array |
224A - Parallelepiped | 964A - Splits |
1615A - Closing The Gap | 4C - Registration System |
1321A - Contest for Robots | 1451A - Subtract or Divide |
1B - Spreadsheet | 1177A - Digits Sequence (Easy Edition) |
1579A - Casimir's String Solitaire | 287B - Pipeline |
510A - Fox And Snake | 1520B - Ordinary Numbers |
1624A - Plus One on the Subset | 350A - TL |
1487A - Arena | 1520D - Same Differences |
376A - Lever | 1305A - Kuroni and the Gifts |
1609A - Divide and Multiply | 149B - Martian Clock |
205A - Little Elephant and Rozdil | 1609B - William the Vigilant |
978B - File Name | 1426B - Symmetric Matrix |